package datastruct.tree;


import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

/**
 * 二分搜索树
 *
 * @author RunningShrimp
 * @date 2021/5/9  20:14
 */
public class BinarySearchTree<E extends Comparable<E>> {
    private TreeNode root;
    private int size;

    public BinarySearchTree() {
        this.root = null;
        this.size = 0;
    }

    public BinarySearchTree(E date) {
        this.root = new TreeNode(date);
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 添加元素
     *
     * @param element
     */
    public void add(E element) {
        root = add(root, element);
    }

    private TreeNode add(TreeNode node, E element) {
        if (node == null) {
            size++;
            return new TreeNode(element);
        }
        if (element.compareTo(node.date) < 0) {
            node.left = add(node.left, element);
        } else if (element.compareTo(node.date) > 0) {
            node.right = add(node.right, element);
        }
        return node;
    }

    /**
     * 是否包含某元素
     *
     * @param e
     * @return
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(TreeNode node, E e) {
        if (node == null) {
            return false;
        }
        if (e.equals(node.date)) {
            return true;
        }
        if (e.compareTo(node.date) < 0) {
            return contains(node.left, e);
        } else {
            return contains(node.right, e);
        }
    }

    /**
     * 后序遍历
     */
    public void postOrderTraversal() {
        postOrderTraversal(root);
    }

    private void postOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        System.out.print(node.date + " ");
    }

    /**
     * 前序遍历
     */
    public void preOrderTraversal() {
        preOrderTraversal(root);
    }

    private void preOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.date + " ");
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

    /**
     * 中序遍历
     */
    public void inOrderTraversal() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.left);
        System.out.print(node.date + " ");
        inOrderTraversal(node.right);
    }

    /**
     * 主要是利用栈的特点，右子树先入栈，左子树后入栈
     */
    public void depthFirstTraversal() {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.date + " ");
            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }

        }
    }

    /**
     * 主要是利用二叉树的特点，不断遍历处理左子树，左子树处理完成在处理右子树，右子树入栈
     */
    public void depthFirstTraversal2() {
        TreeNode node = root;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                System.out.print(node.date + " ");
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }

    public void breadthFirstTraversal() {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 获取最小值
     *
     * @return
     */
    public E minim() {
        if (root == null) {
            return null;
        }
        TreeNode node = minim(root);
        return node.date;
    }


    private TreeNode minim(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return minim(node.left);
    }

    /**
     * 获取最大值
     *
     * @return
     */
    public E maxim() {
        if (root == null) {
            return null;
        }
        TreeNode node = maxim(root);
        return node.date;
    }

    private TreeNode maxim(TreeNode node) {
        if (node.right == null) {
            return node;
        }
        return maxim(node.right);
    }

    public E removeMinim() {
        if (root == null) {
            return null;
        }
        E e = minim();
        root = removeMinim(root);
        return e;
    }

    private TreeNode removeMinim(TreeNode node) {
        if (node.left == null) {
            TreeNode rightNode = node.right;
            node.right = null;
            node = rightNode;
            size--;
            return node;
        }
        node.left = removeMinim(node.left);
        return node;
    }

    public E removeMaxim() {
        if (root == null) {
            return null;
        }
        E e = maxim();
        root = removeMaxim(root);
        return e;
    }

    private TreeNode removeMaxim(TreeNode node) {
        if (node.right == null) {
            TreeNode leftNode = node.left;
            node.left = null;
            node = leftNode;
            size--;
            return node;
        }
        node.right = removeMinim(node.right);
        return node;
    }

    public void remove(E e) {
        //TODO:
        root = remove(root, e);
    }

    private TreeNode remove(TreeNode node, E e) {
        if (node == null) {
            return null;
        }
        if (e.equals(node.date)) {
            if (node.left == null) {
                TreeNode rightNode = node.right;
                node.right = null;
                node = rightNode;
                size--;
                return node;
            }
            if (node.right == null) {
                TreeNode leftNode = node.left;
                node.left = null;
                node = leftNode;
                size--;
                return node;
            }
            TreeNode successor = minim(node);
            successor.right = removeMinim(node);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        } else if (e.compareTo(node.date) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else {
            node.right = remove(node.right, e);
            return node;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBstString(root, 0, res);
        return res.toString();
    }

    /**
     * 生成以node为根节点，深度为depth的描述二叉树的字符串
     *
     * @param node  节点
     * @param depth 深度
     * @param res   字符串拼接类
     */
    private void generateBstString(TreeNode node, int depth, StringBuilder res) {

        if (node == null) {
            res.append(generateDepthString(depth)).append("null\n");
            return;
        }

        res.append(generateDepthString(depth)).append(node.date).append("\n");
        generateBstString(node.left, depth + 1, res);
        generateBstString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth) {
        return "--".repeat(Math.max(0, depth));
    }

    private class TreeNode {
        public E date;
        public TreeNode left;
        public TreeNode right;


        public TreeNode(E date) {
            this(date, null, null);
        }

        public TreeNode(E date, TreeNode left, TreeNode right) {
            this.date = date;
            this.left = left;
            this.right = right;
        }
    }
}
